HackerRank The Maximum Subarray
提出
code: python
import math
import os
import random
import re
import sys
#
# Complete the 'maxSubarray' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#
def maxSubarray(arr):
# Write your code here
subsequence = 0
for i in arr:
if i > 0:
subsequence += i
if subsequence == 0:
subsequence += max(arr)
for i in range(1, len(arr)):
cumu.append(arri + cumu-1) print(cumu)
if __name__ == '__main__':
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = maxSubarray(arr)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
解答
code: python
import math
import os
import random
import re
import sys
#
# Complete the 'maxSubarray' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#
'''
-2 3 5 4 9 109 59 189 99
-2 3 5 5 9 109 109 189 189
'''
def maxSubarray(arr):
# Write your code here
subsequence = 0
for i in arr:
if i > 0:
subsequence += i
if subsequence == 0:
subsequence += max(arr)
# Kadane's Algorithm
max_current = max_global = arr0 for i in range(1, len(arr)):
max_current = max(arri, max_current + arri) max_global = max(max_global, max_current)
if __name__ == '__main__':
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = maxSubarray(arr)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
メモ
https://www.youtube.com/watch?v=86CQq3pKSUw
https://scrapbox.io/files/61d256f628f4e700218b31cb.png
提出
code: python
import math
import os
import random
import re
import sys
#
# Complete the 'maxSubarray' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#
def maxSubarray(arr):
# Write your code here
suba = 0
subs = 0
for i in arr:
if i > 0:
subs += i
if __name__ == '__main__':
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = maxSubarray(arr)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
提出
code: python
import math
import os
import random
import re
import sys
#
# Complete the 'maxSubarray' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#
'''
2
4
1 2 3 4
6
2 -1 2 3 4 -5
subarray sums
-> 10
-2 -3 -1 -4 -6
-> -2 incorrect
subsequence sums
if v > 0: res += v
'''
def maxSubarray(arr):
# Write your code here
if __name__ == '__main__':
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = maxSubarray(arr)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()